/* C++ implementation to convert
infix expression to postfix*/

#include<stack>
#include <string>
#include <iostream>
#include <vector>
#include<math.h>
#include <algorithm>
using namespace std;



// Function to return precedence of operators
int prec(char c)
{
	if (c == '^')
		return 3;
	else if (c == '/' || c == '*')
		return 2;
	else if (c == '+' || c == '-')
		return 1;
	else
		return -1;
}

// Function to return the associativity of operators
bool right2Left(char c)
{
	if (c == '^') {
		return true;
	}
	else {
		return false;
	}
}

string preTreatment(string s) {
	string standard = "";
	// Remove all the blankspace
	s.erase(std::remove(s.begin(), s.end(), ' '), s.end());
	// Add '*' if being omitted
	standard.push_back(s[0]);
	for (int i = 1; i < s.size(); i++) {
		if (s[i] == '(' && ((s[i - 1] == ')' || (s[i - 1] <= '9' && s[i - 1] >= '0')))) {
			standard.push_back('*');
			standard.push_back(s[i]);
			i++;
			standard.push_back(s[i]);
		}
		else {
			standard.push_back(s[i]);
		}
	}
	return standard;
	
}

// The main function to convert infix expression
// to postfix expression
vector<string> infixToPostfix(string s)
{
	s = preTreatment(s);
	stack<char> st; // For stack operations, we are using
	// C++ built in stack
	vector<string> result;
	string temp = "";

	// If the string is empty, throw an exception.
	if (s.empty()) {
		throw "Error: Empty input! ";
	}

	for (int i = 0; i < s.length(); i++) {
		char c = s[i];
		temp = "";

		// If the scanned character is
		// an operand, add it to output string.
		if (c >= '0' && c <= '9') {
			temp += c;
			// If decimal numbers or multi-digit
			while ((s[i + 1] >= '0' && s[i + 1] <= '9') || s[i + 1] == '.') {
				temp += s[i + 1];
				i++;
			}
			if (temp.back() == '.') {
				temp += '0';
			}
			result.push_back(temp);
		}

		// If the scanned character is an
		// ‘(‘, push it to the stack.
		else if (c == '(')
			st.push('(');

		// If the scanned character is an ‘)’,
		// pop and to output string from the stack
		// until an ‘(‘ is encountered.
		else if (c == ')') {
			while (!st.empty() && st.top() != '(' ) {
				temp += st.top();
				result.push_back(temp);
				st.pop();
				temp = "";
			}
			if (st.empty()) {
				throw "Error: Mismatched parentheses!";
			}
			st.pop();
		}

		// If an operator is scanned
		else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
			if (st.empty() || ((prec(c) > prec(st.top())) ||
				(prec(c) == prec(st.top()) && right2Left(c)))) {
				st.push(c);
				continue;
			}
			while (!st.empty() and ((prec(c) < prec(st.top())) ||
				(prec(c) == prec(st.top()) && !right2Left(c)))) {
				temp += st.top();
				st.pop();
				result.push_back(temp);
				temp = "";
			}
			st.push(c);
		}

		else {
			throw "Error: Invalid character input!";
		}

	}

	// Pop all the remaining elements from the stack
	while (!st.empty()) {
		temp = "";
		temp += st.top();
		result.push_back(temp);
		st.pop();
	}

	for (int i = 0; i < result.size(); i++) {
		if (result[i] == "(")
			throw "Error: Mismatched parentheses!";
	}

	return result;
}

void pop2(double& op1, double& op2, stack<double>& operand)
{
	if (operand.size() < 2) {
		throw "Error: Mismatch between operands and operators";
	}

	op2 = operand.top();
	operand.pop();
	op1 = operand.top();
	operand.pop();
}


double evaluate(vector<string> s)
{
	double op1 = 0;
	double op2 = 0;
	stack<double> operand;
	double result;

	for (const string& token : s) {
		if (token == "+") {
			pop2(op1, op2, operand);
			operand.push(op1 + op2);
		}
		else if (token == "-") {
			pop2(op1, op2, operand);
			operand.push(op1 - op2);
		}
		else if (token == "*") {
			pop2(op1, op2, operand);
			operand.push(op1 * op2);
		}
		else if (token == "/") {
			pop2(op1, op2, operand);
			if (op2 == 0) {
				throw "Error: Division by zero!";
			}
			operand.push(op1 / op2);
		}
		else if (token == "^") {
			pop2(op1, op2, operand);
			operand.push(pow(op1, op2));
		}
		else {
			// convert the number string to a double and push to the stack
			operand.push(atof(token.c_str()));
		}
	}

	if (operand.size() > 1) {
		throw "Error: Mismatch between operands and operators!";
	}

	result = operand.top();
	return result;
}

